% Ejercicio "Gramática de los paréntesis"
\subsection*{\fbox{\theejercicio} - Gram\'atica de los par\'entesis}

Consideremos qel lenguaje formando por cadenas balanceadas y par\'entesis () y par\'entesis ``\'angulo'' $<>$. Ejemplos de cadenas v\'alidas son:

\begin{verbatim}
(<>(()))
((<()>))()
( <> (<<( )>>)(()) ) < () (<>) >
\end{verbatim}

No son cadenas v\'alidas, por ejemplo:

\begin{verbatim}
((<))
(<>)(<()>))
(<(>))
\end{verbatim}

En esta \'ultima, aunque hay el mismo n\'umero de par\'entesis de apertura que de cierre, tampoco es v\'alida,
pues el s\'{\i}mbolo ``$>$'' aparece antes de que se hayan cerrado todos los par\'entesis abiertos que aparecen
despu\'es del par\'entesis de apertura que es pareja con \'el: $<(>$

\begin{enumerate}[1)]
\item Escribir una gram\'atica S-atribuida para obtener la diferencia entre el n\'umero de parejas \verb@()@, y el de parejas \verb@<>@.
\item Si se hace un recorrido primero en profundidad del grafo de dependencias, escribe la secuencia de reglas que se ejecutan para la cadena \verb@"( < ( ) > ) ( )"@. Numerar los no terminales seg\'un aparecen en el grafo de dependencias, suponiendo que el \'arbol se construye descendentemente.
\end{enumerate}

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

Apartado 1)

\begin{center}
\begin{tabular}{|l|lcll|} \hline
         &           &               &                   &                             \\
{\tt 1}  & {\em S'}  & $\rightarrow$ & {\em S}           & \{                          \\
         &           &               &                   & \ \ \ $S'.d = S.p - S.a$    \\
         &           &               &                   & \}                          \\
         &           &               &                   &                             \\
{\tt 2}  & {\em S}   & $|$           & {\em S$_1$ S$_2$} & \{                          \\
         &           &               &                   & \ \ \ $S.p = S_1.p + S_2.p$ \\
         &           &               &                   & \ \ \ $S.a = S_1.a + S_2.a$ \\
         &           &               &                   & \}                          \\
{\tt 3}  & {\em S}   & $|$           & ( {\em S$_1$} )   & \{                          \\
         &           &               &                   & \ \ \ $S.p = S_1.p + 1$     \\
         &           &               &                   & \ \ \ $S.a = S_1.a$         \\
         &           &               &                   & \}                          \\
{\tt 4}  & {\em S}   & $|$           & ( )               & \{                          \\
         &           &               &                   & \ \ \ $S.p = 1$             \\
         &           &               &                   & \ \ \ $S.a = 0$             \\
         &           &               &                   & \}                          \\
{\tt 5}  & {\em S}   & $|$           & {\em $<$ S$_1 >$} & \{                          \\
         &           &               &                   & \ \ \ $S.p = S_1.p$         \\
         &           &               &                   & \ \ \ $S.a = S_1.a + 1$     \\
         &           &               &                   & \}                          \\
{\tt 6}  & {\em S}   & $|$           & $< >$             & \{                          \\
         &           &               &                   & \ \ \ $S.p = 0$             \\
         &           &               &                   & \ \ \ $S.a = 1$             \\
         &           &               &                   & \}                          \\ \hline
\end{tabular}
\end{center}

Apartado 2)

\medskip

$S_4.p = 1$       \\
$S_4.a = 0$       \\
$S_3.p = S_4.p$   \\
$S_3.a = S_3.a+1$ \\
$S_1.p = S_3.p+1$ \\
$S_1.a = S_3.a$   \\
$S_2.p = 1$       \\